package com.huawei.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author: liu.cheng.su
 * @Time: 2023/12/12 0012 20:26
 * @Description:
 */
public class Code1005 {
    public static void main(String[] args) {
        int[] nums = {2, -3, -1, 5, -4};
        System.out.println(largestSumAfterKNegations(nums, 2));
        System.out.println(largestSumAfterKNegations2(nums, 2));
    }

    public static int largestSumAfterKNegations2(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int ans = Arrays.stream(nums).sum();
        for (int i = -100; i < 0; ++i) {
            if (freq.containsKey(i)) {
                int ops = Math.min(k, freq.get(i));
                ans += (-i) * ops * 2;
                freq.put(i, freq.get(i) - ops);
                freq.put(-i, freq.getOrDefault(-i, 0) + ops);
                k -= ops;
                if (k == 0) {
                    break;
                }
            }
        }
        if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
            for (int i = 1; i <= 100; ++i) {
                if (freq.containsKey(i)) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        return ans;
    }


    public static int largestSumAfterKNegations(int[] nums, int k) {
        int min = nums[0];
        List<Integer> list = new ArrayList<>();
        int maxSum = 0;

        for (int i = 0; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
            if (nums[i] < 0) {
                list.add(nums[i]);
            }
        }
        if (min == 0) {
            maxSum = Arrays.stream(nums).sum();
        } else if (min > 0) {
            if (k % 2 == 1) {
                maxSum = Arrays.stream(nums).sum() - min - min;
            } else {
                maxSum = Arrays.stream(nums).sum();
            }
        } else {
            //min<0 因此 list.size() > 0
            if (k == list.size()) {
                maxSum = Arrays.stream(nums).sum() - 2 * (list.parallelStream().mapToInt(Integer::intValue).sum());
            } else if (k < list.size()) {
                maxSum = getSumWhenKSmaller(nums, list, k);
            } else {
                maxSum = getSumWhenKBigger(nums, list, k);
            }
        }
        return maxSum;
    }

    private static int getSumWhenKBigger(int[] nums, List<Integer> list, int k) {
        if (contains0(nums)) {
            return Arrays.stream(nums).sum() - 2 * (list.parallelStream().mapToInt(Integer::intValue).sum());
        }

        int v = 0;
        int n = k - list.size();
        int minAbsOfNums = Math.abs(nums[0]);
        for (int num : nums) {
            if (minAbsOfNums > Math.abs(num)) {
                minAbsOfNums = Math.abs(num);
            }
        }
        int sum = Arrays.stream(nums).sum() - 2 * (list.parallelStream().mapToInt(Integer::intValue).sum());
        if (n % 2 == 0) {
            v = sum;
        } else {
            v = sum-2*minAbsOfNums;
        }
        return v;
    }

    private static boolean contains0(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                return true;
            }
        }
        return false;
    }

    private static int getSumWhenKSmaller(int[] nums, List<Integer> list, int k) {
        int v = 0;
        Collections.sort(list);

        for (int i = 0; i < list.size(); i++) {
            if (i >= k) {
                v += list.get(i);
            } else {
                v -= list.get(i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                v += nums[i];
            }
        }
        return v;
    }

}
